package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.swing.tree.TreeNode;

/**
 * https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/2/
 * <p>
 * 解题：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode/
 */
public class 中序遍历 extends 二叉树Case {
	@Test
	public void test() {
//		1
//       \
//		  2
//		 /
//		3
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = node1.right = new TreeNode(2);
		TreeNode node3 = node2.left = new TreeNode(3);

		Assert.assertEquals(Arrays.asList(1, 3, 2), preorderTraversal(node1));
	}

	/**
	 * 前序遍历 递归
	 *
	 * @param root
	 *
	 * @return
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		help(root, res);
		return res;
	}

	private void help(TreeNode node, List<Integer> res) {
		if (node == null) {
			return;
		}

		if (node.left != null) {
			help(node.left, res);
		}

		res.add(node.val);

		if (node.right != null) {
			help(node.right, res);
		}
	}
}
